In the case of maintaining important secret data (referred hereafter as original data), there are potential threats such as loss, destruction, theft and privacy violation. Such threats cannot be prevented by simply encrypting the data to be maintained in secret, and it is effective to produce plural copies in anticipation of the loss or destruction, but the production of plural copies increases a risk of the theft.
As a conventional method for resolving such a problem, there is a threshold secret sharing scheme (see A. Shamir “How to Share a Secret”, Comm. Assoc. Comput. Mach., Vol. 22, no. 11, pp. 612-613 (November 1979), for example). In this conventional method, the original data S is divided into n sets of divided data, and the original data S can be recovered by collecting at least a certain number x sets of the divided data among the n sets of the divided data, but the original data S cannot be recovered by collecting only x-1 sets of the divided data. Consequently, the original data S is not leaked even if as many as x-1 sets of the divided data are stolen, and the original data S can be recovered even if as much as n-x sets of the divided data are lost or destroyed.
As a representative example for realizing this method, there is a method using (n−1)-th degree polynomial and the residue calculation (see Bruce Schneier “Applied Cryptography”, John Wiley & Sons, Inc., pp. 383-384 (1994)., for example). This conventional method has been utilized in the divisional management of a secret key of the public key cryptosystem, where the amount of data to be maintained is not so large so that it does not cause any problem in terms of the calculation processing power of the current computer and the cost of the memory device or medium.
However, when this conventional method is utilized in the case where the amount of data to be maintained safely becomes Megabytes, Gigabytes or even greater, it will require a calculation processing power capable of carrying out the calculation processing of multiple length integers including the polynomial calculation and the residue calculation with respect to a huge amount of data. Moreover, in this conventional method, five divided data of one byte length are generated from data of one byte length in the case where the number of division n is 5, so that it will require a large memory capacity that is linearly proportional to the number of division with respect to the original data. Thus there has been a problem that it is impractical to realize the conventional method by using the computer.
Also, in the conventional method described above, a unit of processing for the division calculation is set up in order to secure the secrecy of the data, but this unit of processing for the division calculation requires a certain data length, and there has been a problem that the division calculation cannot be carried out at arbitrary unit of processing.